/*
Date:20210521 0:00AM
key:经典动态规划，区别在于先导出i从1-sqrt(n)+1的平方数组
*/
class Solution {
public:
    int numSquares(int n) 
    {
        vector<int>v;
        int i=1;
        //这个sqrt(n)+1的+1特别关键
        int n1=sqrt(n)+1;
        while((i)<n1)
        {
            //cout<<i;
            v.push_back(i*i);
            i++;
        }
        int*dp=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<n+1;i++)
        {
            int Min=INT_MAX;
            for(int&g:v)
            {
                if(i-g>-1)
                {
                    Min=min(Min,dp[i-g]);
                }
                
            }
            dp[i]=Min+1;
            //cout<<i<<" "<<dp[i]<<" "<<endl;
        }
        return dp[n];
    }
};